A common method of encrypting a plaintext message starts by substituting integers for plaintext characters according to some standard alphabet such as ITA2, ITA5, ASCII, or EBCDIC. These integers are then written in binary form to create a first string, or sequence, of 0's and 1's. The first string is modulo 2-added to another, second sequence of 0's and 1's to produce a third sequence of 0's and 1's. The third sequence of 0's and 1's is transmitted as the encrypted message. The sender's object is to make this third string of 0's and 1's appear to be a random sequence of digits in binary form. The intended receiver modulo 2-adds the second sequence to the third sequence to recover the first sequence. Thereafter, the original plaintext message is derived from the standard alphabet that was used, e.g., ITA2, ITA5, ASCII, or EBCDIC. If the second sequence is truly random, an interceptor-attacker will be unable to reproduce the first sequence. Thus, the plaintext message is preserved.
There are a number of problems with this scheme: First, random number strings are a relatively scarce commodity. Second, the receiver must have at hand exactly the same random number sequence the sender used or must be able to reproduce it. Having at hand exactly the same random number sequence the sender used requires the sharing of an enormous amount of key material. The sharing of an enormous amount of key material is impractical. Reproducing exactly the same random number sequence the sender used is impossible.
To avoid these two difficulties, a pseudo-random number generator is commonly employed by both sender and receiver. A pseudo-random number generator is a deterministic machine which, when initialized by a "seed" number, produces a string of digits which appears to be random (by passing various statistical tests). The output of a pseudo-random number generator is periodic, but the period can be made very long. When sender and receiver use pseudo-random number generators to produce the second, key, or encrypting sequence, they start with a common initializing "seed" and synchronize the outputs of their generators. Starting with a common initializing "seed" and synchronizing the outputs of the generators allows a known plaintext attack in which an interceptor-attacker gains access to plaintext (hence to its binary digit string equivalent in terms of some standard numerical alphabet) and to the corresponding ciphertext. Knowing the digits of the binary plaintext string enables the attacker to reproduce the corresponding pseudo-random number sequence. This frequently allows the attacker to determine the algorithm, initializing "seed," and output sequence of the system's pseudo-random number generator, thus "breaking" the code.
In U.S. Pat. No. 5,113,444, entitled "Random Choice Cipher System and Method," issued to the same inventor as that of the present invention and incorporated herein by reference (which may be referred to as the random choice system or the random choice method), a string of random digits is added to a string of integers numerically coding the plaintext characters of a message. The summed integer is the body of the cryptogram.
The numerical codings, referred to as numerical synonyms, are randomly chosen from large, randomly dispersed collections of such integers corresponding to the plaintext alphabet characters. The collections of randomly distributed numerical synonyms and their matchings to the characters of a plaintext alphabet comprise a thesaurus which must be shared by a sender-receiver pair. A masking tape must also be shared between sender and receiver. A masking tape comprises a long string of random digits from which the string of random digits, to be added to the numerical coding of the message, is selected.
Another cipher scheme, by the same inventor as that of the present invention, teaches a "Random Coding Cipher System and Method," copending U.S. patent application Ser. No. 07/953,521, incorporated herein by reference and may be referred to herein as the random coding system or the random coding method. This scheme dispenses with the thesaurus, using instead one-time numerical codings for alphabet characters which are themselves extracted from the masking tape. The plaintext message string formed with these numerical codings is then added to a string of digits from the masking tape to form the ciphertext string.
Like this random coding cipher system, the present invention utilizes only a long shared masking tape, but, unlike the random coding cipher system, it does not change numerical codings of plaintext alphabet characters with each message.
The present invention thus provides a variant of the famous "one-time pad" system of Vernam. In the Vernam system, sender and receiver share an alphabet, A, the set of characters of which has cardinality .vertline.A.vertline., and positive integer codings, also 1, . . . , .vertline.A.vertline., for each of the alphabet characters. Sender and receiver also share a long string, S, of randomly recurring integers, 1, . . . , .vertline.A.vertline..
To send a first message, the sender adds, modulo .vertline.A.vertline., the first integer from S and the numerical coding of the first plaintext character of this first message. Likewise, for the next integer for transmission, the sender adds, modulo .vertline.A.vertline., the second integer of S and the numerical coding of the second character of the message, etc. The resultant concatenated string of sums, representing random replacements of alphabet characters by others, constitutes the cryptogram. The receiver subtracts the corresponding sequence of integers from S to recover the agreed-upon numerical coding of the original message. The string of integers from S for the second message starts where that of the first message left off, etc. Hence the name of the method (one-time pad)--as key material from S is used, it is discarded. Attempts to avoid frequent exchanges of strings S have heretofore involved substituting synchronized pairs of pseudo-random number generators for the integer strings S, as remarked above.
The present invention differs from the one-time pad in major ways: First, the shared integer string (herein called the masking tape) can be used indefinitely since the location of the masking tape string integer is arbitrary and concealed from an attacker.
Second, the numerical codings of plaintext characters are effectively changed, from the viewpoint of an attacker, whenever spurious digits are interspersed in the ciphertext string. Third, like its predecessors, the random choice system and the random coding system, the present invention provides for block permutations of segments of the ciphertext string.
These distinctions will be made more apparent in the detailed description of the invention given below.